package main

import "fmt"

/**
找1...n字典序的第K小数字
https://www.youtube.com/watch?v=yMnR63e3KLo
https://leetcode-cn.com/problems/k-th-smallest-in-lexicographical-order/solution/ben-ti-shi-shang-zui-wan-zheng-ju-ti-de-shou-mo-sh/
![](http://cdn.bsummer.cn/20210304011435.png)
什么是字典序？
简而言之，就是根据数字的前缀进行排序，
比如 10 < 9，因为 10 的前缀是 1，比 9 小。
再比如 112 < 12，因为 112 的前缀 11 小于 12。

		1						2               3            4            ...           9
	10 11 12 13 .. 19      20 21 22

简单理解:
k大于当前树节点数量时，cur向右移动
k小于当前树节点数量时，cur向下移动
在不断向右、向下的过程下找到目标
*/

func main() {
	r := findKthNumber(13, 4)
	fmt.Println(r)
}

func findKthNumber(n int, k int) int {
	cur := 1 //起始树根节点值
	for {
		count := getCount(cur, n) // 获取以值cur为根的子树节点数
		if k > count {            // 判断第k个节点是否在cur为根的子树中，k>count表示不在该子树，切至下一个节点判断(k-=count,cur++),否则表示第k个元素在该子树上,如果k>1,则k--,cur*=10 直至k==1，此时当前节点cur即为第k个节点
			k -= count
			cur++
		} else {
			if k > 1 { //缩小搜索范围 当前层一定只有一个，于是到下一层继续查找
				cur *= 10
				k--
			} else { // k==1时 表示第一个节点，也就是当前节点cur
				break
			}
		}
	}
	return cur
}

// 获取树的节点个数 每层节点数加一起就是树的节点数 i是当前树的根节点值 n是所有节点的数量
func getCount(i, n int) int {
	// i表示当前层的第一个节点 j表示隔壁下一棵树的第一个节点
	j := i + 1
	count := 0
	for i <= n { // n是自然顺序最大的数 记得这里有等于号！
		count += min(j-1, n) - i + 1 // 当前层节点数：同层最后一个节点-第一个节点+1 等于该层节点数 最后一个节点=min(该层最大值,n)
		i *= 10                      //i下一层第一个节点i=i*10
		j *= 10                      //j下一层第一个节点j=j*10
	}

	return count
}

func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}
